package com.my.test.array;

public class CountOne {

	/**
	 * Count how many 1 occurs from <code>start</code> to <code>end</code>. For
	 * example: 1 to 12 : 1,10,11,12, totally 5 occurrences.
	 * countOneOccurrence(start, end) =
	 * 
	 * @param n
	 * @return
	 */
	public static int countOneOccurrence(int start, int end) {
		if(start >= 0 && end < 10) return 1;
		int tmpEnd = (end / (int) Math.pow(10.0, getNumDigits(end)))
				* (int) Math.pow(10.0, getNumDigits(end));
		int tmpStart = (int) Math.pow(10.0, getNumDigits(end));
		int prefixCnt = countOneOccurrence(0, tmpStart - 1);
		int midCnt = countOneOccurrence(tmpStart, tmpEnd);
		int postCnt = countOneOccurrence(tmpEnd + 1, end);
		return prefixCnt + midCnt + postCnt;
	}

	private static int getNumDigits(int n) {
		String strN = String.valueOf(n);
		return strN.length();
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub

	}

}
